package leetcode.code0773;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution2 implements IDebug {

	// 四方遍历数组，{左，右，上，下}
	static int[] d = new int[] { 0, -1, 0, 1, -1, 0, 1, 0 };

	int limit = 0b111111111111111111;

	int one = 0b111;

	static List<Integer>[] ways;

	static {
		ways = new ArrayList[6];
		for (int i = 0; i < 6; i++) {
			ways[i] = new ArrayList<>();
		}
		for (int x = 0; x < 2; x++) {
			for (int y = 0; y < 3; y++) {
				int index = index(x, y);
				for (int i = 0; i < 8; i += 2) {
					int nextx = x + d[i], nexty = y + d[i + 1];
					if (nextx >= 0 && nextx < 2 && nexty >= 0 && nexty < 3) {
						int nextIndex = index(nextx, nexty);
						ways[index].add(nextIndex);
					}
				}
			}
		}
	}

	public int slidingPuzzle(int[][] board) {
		int init = 0;
		int pos0 = 0;
		int m = board.length, n = board[0].length;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				int cur = board[i][j];
				init <<= 3;
				init |= cur;
				if (board[i][j] == 0) {
					pos0 = index(i, j);
				}
			}
		}
		if (init == 0b1010011100101000) {
			return 0;
		}
		Integer[] times = new Integer[1 << 18];
		times[init] = 0;
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { pos0, init });
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int pos = cur[0], status = cur[1];
			int nextTime = times[status] + 1;
			List<Integer> way = ways[pos];
			for (Integer nextPos : way) {
				int nextStatus = this.swap(status, pos, nextPos);
				if (nextStatus == 0b1010011100101000) {
					return nextTime;
				}
				if (times[nextStatus] == null) {
					times[nextStatus] = nextTime;
					queue.add(new int[] { nextPos, nextStatus });
				}
			}
		}
		return -1;
	}

	// 二维转一维
	public static int index(int x, int y) {
		return x * 3 + y;
	}

	private int swap(int status, int a, Integer b) {
		int numa = pick(status, a);
		int numb = pick(status, b);
		status = clear(status, a, b);
		status = add(status, b, numa);
		status = add(status, a, numb);
		return status;
	}

	// status的a段加上muna状态。段从左到右依次是0，1，2，3，4，5，每一段是三位
	private int add(int status, int a, int numa) {
		return status | (numa << move(a));
	}

	// 将status的，a，b段清空为000
	private int clear(int status, int a, Integer b) {
		status = status & clearAnd(a);
		status = status & clearAnd(b);
		return status;
	}

	private int clearAnd(int pos) {
		return (limit << (move(pos) + 3)) | ((1 << move(pos)) - 1);
	}

	// 第pos段向左移动的步数
	private int move(int pos) {
		int ans = (5 - pos) * 3;
		return ans;
	}

	// 摘出status的pos段内容
	private int pick(int status, int pos) {
		int move = move(pos);
		int num = (one << move) & status;
		return num >> move;
	}

//	// 在status状态下，从零在pos位置，到下一个位置的可能集合。
//	private Map<Integer, Integer> nexts(int pos, int status, List<Integer>[] ways) {
//		List<Integer> way = ways[pos];
//		Map<Integer, Integer> ans = new HashMap<>();
//		for (Integer next : way) {
//			int nextStatus = this.swap(status, pos, next);
//			ans.put(nextStatus, next);
//		}
//		return ans;
//	}

//	// 按照位置组织转移路径集合
//	public List<Integer>[] ways() {
//		List<Integer>[] ans = new ArrayList[6];
//		for (int i = 0; i < 6; i++) {
//			ans[i] = new ArrayList<>();
//		}
//		for (int x = 0; x < 2; x++) {
//			for (int y = 0; y < 3; y++) {
//				int index = this.index(x, y);
//				for (int i = 0; i < 8; i += 2) {
//					int nextx = x + d[i], nexty = y + d[i + 1];
//					if (nextx >= 0 && nextx < 2 && nexty >= 0 && nexty < 3) {
//						int nextIndex = this.index(nextx, nexty);
//						ans[index].add(nextIndex);
//					}
//				}
//			}
//		}
//		return ans;
//	}

	// 0的位置
//	private int pos0(int[][] board) {
//		int m = board.length, n = board[0].length;
//		for (int i = 0; i < m; i++) {
//			for (int j = 0; j < n; j++) {
//				if (board[i][j] == 0) {
//					return this.index(i, j);
//				}
//			}
//		}
//		return 0;
//	}

	@Override
	public void debug4() {
		HelpDebug.compare(1, this.slidingPuzzle(HelpDebug.str2array1("[[1,2,3],[4,0,5]]")));
		HelpDebug.compare(-1, this.slidingPuzzle(HelpDebug.str2array1("[[1,2,3],[5,4,0]]")));
		HelpDebug.compare(5, this.slidingPuzzle(HelpDebug.str2array1("[[4,1,2],[5,0,3]]")));
		HelpDebug.compare(14, this.slidingPuzzle(HelpDebug.str2array1("[[3,2,4],[1,5,0]]")));
//		this.slidingPuzzle(H.str2array1("[[1,2,3],[4,5,0]]"));
//		int hash = this.hash(H.str2array1("[[1,2,3],[4,5,0]]"));
//		System.out.println(Integer.toBinaryString(hash));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
